package Day11;

import java.util.Scanner;

public class Main {

    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int max = 0;
        int cur = 0;

        while (n != 0) {
            cur = 0;
            while (n % 2 != 0) {
                cur++;
                n >>= 1;
            }
            n >>= 1;
            max = Math.max(max, cur);
        }

        System.out.println(max);
    }

    public static void main(String[] args) {
        int ret = getLCA(2,3);
        System.out.println(ret);
    }

    public static int getLCA (int a, int b) {
        while (a != b) {
            while (a < b) {
                b /= 2;
            }
            while (a > b) {
                a /= 2;
            }
        }
        return a;
    }


    public static int getLCA1(int a, int b) {
        return getLCA(1, a, b);
    }

    public static int getLCA (int root, int a, int b) {
        if (root == a|| root == b) {
            return root;
        }

        int edge = root * 2 + 2;
        int aLevel = 2;
        while (edge < a) {
            edge = edge * 2;
            aLevel++;
        } //循环结束后a < edge
        boolean aAtRight = false;
        if (a > edge - aLevel) {
            aAtRight = true;
        }

        edge = root * 2 + 2;
        int bLevel = 2;
        while (edge < b) {
            edge = edge * 2;
            bLevel++;
        } //循环结束后a < edge
        boolean bAtRight = false;
        if (b > edge - bLevel) {
            bAtRight = true;
        }

        //a b在异侧, 返回root
        if (bAtRight && !aAtRight || !bAtRight && aAtRight) {
            return root;
        } else if (bAtRight && aAtRight) {
            if (aLevel < bLevel) {
                return a;
            } else if (aLevel > bLevel) {
                return b;
            } else {
                return getLCA(root * 2 + 1, a, b);
            }
        } else {
            if (aLevel < bLevel) {
                return a;
            } else if (aLevel > bLevel) {
                return b;
            } else {
                return getLCA(root * 2, a, b);
            }
        }

    }

}
